int mySqrt(int x){
    long long max = x / 2;
    long long i;
    long long left = 0, rgith = x;
    if(x == 1 || x == 2 || x == 3) {
        return 1;
    }
    while(left < rgith) {
        if(left == rgith - 1) {
            if(rgith * rgith < x) {
                return rgith;
            }
            else {
                return left;
            }
        }
        else {
            long long mid = (left + rgith) / 2;
            if(mid * mid == x) {
                return mid;
            }
            else if(mid * mid > x) {
                rgith = mid;
            }
            else {
                left = mid;
            }
        }
    }
    return 0;
}